# coding: utf-8

import random
from graph import Hierarchy, vertex_t, vertex_map, T
from .CrossingReduction import CrossingReduction

"""
 * Barycentric heurictic for crossing reduction.
 * Vertices on each layer are order based on their barycenters - the average position of their neighbours.
"""


class BarycentricHeuristic(CrossingReduction):

    def __init__(self):
        self.random_iters = 1  # 可修改
        self.forgiveness = 7
        self.trans = True
        self.min_cross = 0
        # self.mt = random.Random()

        # self.vertex_map_pos = vertex_map[int](g, 'pos', None)
        # for u in g.get_all_nodes():
        #     self.vertex_map_pos[u] = h.get_pos(u)
        # print(h.layers)

    def __del__(self):
        pass

    def run(self, h: Hierarchy) -> None:
        g = h.graph()
        self.best_order = vertex_map[int](g, "best_order", -1)
        self.local_order = vertex_map[int](g, "local_order", -1)
        self.weights = vertex_map[float](g, "weights", 0.0)
        self.eligible = vertex_map[bool](g, "eligible", True)

        self.min_cross = self.init_order(h)

        # TODO
        # self.best_order = h.pos
        for u in g.get_all_nodes():
            self.best_order[u] = h.get_pos(u)
            # print('qqqqqqqqqqqqqqqqqqqqqqqqq',u,h.get_pos(u))
            # print(u,self.weights[u])

        base = self.min_cross

        for i in range(self.random_iters):
            self.reduce(h, base)

            if i != self.random_iters - 1:
                for layer in h.layers:
                    # std::shuffle(l.begin(), l.end(), mt);
                    random.shuffle(layer)
                h.update_all_nodes_pos()
                base = self.init_order(h)

        for u in g.get_all_nodes():
            h.get_layer(u)[self.best_order[u]] = u

        h.update_all_nodes_pos()
        # TODO  测试的结果值
        # for u in h.layers:
        #     print(u)  # 打印出每层有哪些节点

    def init_order(self, h: Hierarchy):
        self.barycenter(h, 0)
        return h.count_crossings()

    # attempts to reduce the number of crossings

    def reduce(self, h: Hierarchy, local_min: int):

        # TODO
        g = h.graph()
        for u in g.get_all_nodes():
            self.local_order[u] = h.get_pos(u)

        # print(self.local_order)
        fails: int = 0
        # TODO
        for i in range(100000):
            self.barycenter(h, i)
            if self.trans:
                #   ifdef FAST
                # self.fast_greedy_switch_heuristic(h)
                #   else
                self.greedy_switch_heuristic(h)
            #   endif
            cross = h.count_crossings()
            #   std::cout << cross << "\n";
            if cross < local_min:
                fails = 0
                # TODO
                for u in g.get_all_nodes():
                    self.local_order[u] = h.get_pos(u)
                local_min = cross
            else:
                fails += 1
            if fails >= self.forgiveness:
                break
        if local_min < self.min_cross:
            self.best_order = self.local_order
            self.min_cross = local_min

    #   ifdef REPORTING
    # report::iters += i;
    # report::random_final.push_back(local_min);
    #   endif
    # TODO  h.set_weights
    def barycenter(self, h: Hierarchy, i: int) -> None:

        if i % 2 == 0:  # top to bottom
            for j in range(1, h.size()):
                self.reorder_layer(h, self.weights, j, True)

        else:  # from bottom up
            for j in range(h.size() - 2, -1, -1):
                self.reorder_layer(h, self.weights, j, False)

    # TODO  h.pos 考虑能不在再写一个 vertex_map 其与h.pos的数值相等

    def reorder_layer(
        self, h: Hierarchy, weights: vertex_map, i: int, downward: bool
    ) -> None:
        g = h.graph()
        # for u in g.get_all_nodes():
        #     self.vertex_map_pos[u] = h.get_pos(u)
        layer = h.layers[i]
        for u in layer:
            weights[u] = self.weight(
                h, u, g.in_neighbours(u) if downward else g.out_neighbours(u)
            )

        layer.sort(key=lambda u: weights[u])
        h.update_all_nodes_pos()

    # calculates the weight of vertex as an average of the positions of its neighbour

    def weight(self, h: Hierarchy, u: vertex_t, neighbours: T):

        count = 0
        sum_ = 0
        for v in neighbours:
            sum_ += h.get_pos(v)
            count += 1

        if count == 0:
            return h.get_pos(u)

        return sum_ / count

    # Heuristic for reducing crossings which repeatedly attempts to swap all ajacent vertices.
    def greedy_switch_heuristic(self, h: Hierarchy):
        improved: bool = True
        k: int = 0
        while improved:
            improved = False
            for layer in h.layers:
                for i in range(len(layer) - 1):
                    old = h.crossing_number(layer[i], layer[i + 1])
                    # print('old', old)
                    next = h.crossing_number(layer[i + 1], layer[i])
                    # print('next', next)
                    # diff = old - next
                    if old > next:
                        improved = True
                        h.swap_node(layer[i], layer[i + 1])

            k += 1

    def fast_greedy_switch_heuristic(self, h: Hierarchy) -> None:
        g = h.graph()

        improved: bool = True
        iters: int = 0
        while improved:
            iters += 1
            improved = False
            for layer in h.layers:
                assert len(layer) >= 1
                for i in range(len(layer) - 1):
                    if self.eligible.at(layer[i]):
                        old: int = h.crossing_number(layer[i], layer[i + 1])
                        next: int = h.crossing_number(layer[i + 1], layer[i])
                        diff: int = old - next
                        if diff > 0:
                            # print(layer[i], 'x', layer[i + 1], ' ', end='')
                            # print('old:', old, 'next:', next_)
                            improved = True
                            # before = h.count_crossings()
                            h.swap_node(layer[i], layer[i + 1])
                            # assert before - diff == h.count_crossings()
                            # min_cross -= diff
                            if i > 0:
                                self.eligible.set(layer[i - 1], True)
                            self.eligible.set(layer[i + 1], True)
                            for u in g.neighbours(layer[i]):
                                self.eligible.set(u, True)
                            for u in g.neighbours(layer[i + 1]):
                                self.eligible.set(u, True)
                        self.eligible.set(layer[i], False)
            # print('')
        # print(k, 'k')
